using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;
using System.Threading;

namespace SuchAlgorithmen
{
    public class QuickSort : SuchAlgorithmen.ISorter
    {
        private ArrayList _liste;
        

        /// <summary>
        /// Konstruktor der Klasse Quicksort, es wird als Parameter eine Liste verlangt, die
        /// in der weiteren Anwendung benutzt wird
        /// </summary>
        /// <param name="array">Das zu sortierende Array</param>
        public QuickSort(ArrayList array)
        {
            _liste = new ArrayList(array);
        }

        #region ISorter Member

        //public Methoden
        /// <summary>
        /// Sortiert die Liste
        /// </summary>
        /// <returns>void</returns>
        public void Sort()
        {
            RekursionHandler(0, _liste.Count - 1);
        }

        /// <summary>
        /// Gibt den Wert in der Liste mit index i 
        /// </summary>
        /// <param name="index">Index i</param>
        /// <returns>int Den Wert in der Liste mit index i</returns>
        public int this[int index]
        {
            get { return (int)_liste[index]; }
        }
        #endregion

        //private Methoden
        private int Partition(int left, int right)
        {
            int i = left - 1;
            int j = right;
            while (i < j)
            {
                do
                {
                    i++;
                } while (i < right && (int)_liste[i] <= (int)_liste[right]);
                do
                {
                    j--;
                } while (j > 0 && (int)_liste[j] >= (int)_liste[right]);
                if (i < j)
                {
                    Swap(i, j);
                }
            }
            Swap(i, right);
            return i;
        }

        private void RekursionHandler(int left, int right)
        {
            if (left < right)
            {
                int median = Partition(left, right);
                RekursionHandler(left,median-1);
                RekursionHandler(median+1,right);
            }
        }

        private void Swap(int i, int j)
        {
            int z = (int)_liste[i];
            _liste[i] = _liste[j];
            _liste[j] = z;
        }

      
    }
}
